package com.lw.leetcode.arr.b;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * arr
 * 2250. 统计包含每个点的矩形数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/9/10 9:20
 */
public class CountRectangles {


    public static void main(String[] args) {
        CountRectangles test = new CountRectangles();

        // {2,1}
//        int[][] rectangles = {{1, 2}, {2, 3}, {2, 5}};
//        int[][] points = {{2, 1}, {1, 4}};

        // {1,3}
        int[][] rectangles = {{1, 1}, {2, 2}, {3, 3}};
        int[][] points = {{1, 3}, {1, 1}};

        int[] ints = test.countRectangles(rectangles, points);

        System.out.println(Arrays.toString(ints));
    }


    public int[] countRectangles(int[][] rectangles, int[][] points) {
        List<Integer>[] arr = new ArrayList[101];
        for (int i = 0; i <= 100; i++) {
            arr[i] = new ArrayList();
        }
        for (int[] rectangle : rectangles) {
            int t = rectangle[0];
            for (int i = 1; i <= rectangle[1]; i++) {
                arr[i].add(t);
            }
        }
        for (List<Integer> list : arr) {
            Collections.sort(list);
        }
        int length = points.length;
        int[] items = new int[length];
        for (int i = 0; i < length; i++) {
            int[] as = points[i];
            items[i] = find(arr[as[1]], as[0] - 1);
        }
        return items;
    }

    private int find(List<Integer> list, int t) {
        int st = 0;
        int end = list.size() - 1;
        if (end == -1 || list.get(end) <= t) {
            return 0;
        }
        while (st < end) {
            int m = st + ((end - st) >> 1);
            int v = list.get(m);
            if (v <= t) {
                st = m + 1;
            } else {
                end = m;
            }
        }
        return list.size() - st;
    }

}
